1. Technical Field
The present invention relates to a serial of transfer protocols for high-quality and high-speed data transfer in data networks, especially wireless or mobile networks, and more particularly, relates to performance enhancement of Transmission Control Protocol (TCP) for wireless network applications.
2. Related Art
A data network is a collection of network devices, or nodes interconnected by point-to-point links. Communication links may be wired (i.e., optical fiber) or wireless (i.e., infrared or radio-frequency) for supporting a number of logical point-to-point channels. Each channel may be a bi-directional communication path for allowing commands and message data to flow between two network devices or nodes within the data network. Network devices or nodes may be categorized as either end systems or routers, which are also known as intermediate systems or communication gateways. End systems may include PCs, workstations, mainframes, file servers, storage devices and other types of computers. Router may include a number of communication links for forwarding data arriving over one link onto another link for transmission to an end system or another router.
Generally, end systems both send data to other end stations on the data network and receive data sent by other end systems on the data network. When an end system serves as a sender of data, it is referred to as a source for that data; whereas, when such an end station serves as a receiver of data, it is referred to as a destination for the data. Typically, end systems may act as both sources and destinations depending upon whether they are sending or receiving data. When acting as a source, the end system sends data in the form of messages over a communication link to a router for transferring the messages to an end system or another router.
Each message may comprise a sequence of information bits. Typically, however, the messages sent over the data network are not sent as a continuous, uninterrupted stream of bits. Rather, they are divided up into smaller blocks of information called packets, which are then transmitted individually. Each packet has a predetermined maximum length. In addition to a data field which contains the data to be transferred, a packet also includes a header field which contains control information such as format, identifiers which indicate what portion of the message is contained in the packet, the source of the packet and the intended destination of the packet. When the packets which together contain a message reach the destination, the destination processes them by assembling their data fields into proper order to reconstruct the full message.
One important design objective in data networks is controlling the flow of packets so that such packets may not be transmitted at a faster rate than they can be processed by the routers through which the packets may pass or by the destinations. Even in the simplest data network consisting of two end systems interconnected by a router, for example, the source may flood the destination if it transmits packets faster than they can be processed by the destination. In more complicated networks consisting of many end systems, numerous routers and alternative communication paths between the end systems, the likelihood of problems from excess communication traffic is significantly greater. This becomes especially true as the number of active end systems on the network increases and if communication speeds of the equipment within the network are mismatched. A mismatch may exist if, for example, a router cannot transfer packets as fast as they are being sent to it by the source. A mismatch may also exist between the speed at which the link can transmit packets, namely the link speed, and the rate at which the router can transfer packets. Predictably, as the complexity of the network increases, achieving an acceptable traffic control also becomes more difficult.
On most networks, including TCP/IP packet-switched networks in which Transmission Control Protocol (TCP) [RFC 793, September 1981] may be implemented to ensure high-speed and high-quality data transfer in the Internet, at least two basic mechanisms are normally used for dealing with excess traffic arriving at a destination. One mechanism involves the use of buffers and the other involves flow control. In buffered systems, both the routers and the end systems are provided with buffer memory to handle overloads. Arriving traffic which exceeds the processing rate of the device is temporarily stored in the buffer memory until the device can process it. Buffers offer a satisfactory solution to excess traffic problems only if the overload is transitory. If the overload persists for too long, the buffers may become full after which the additional packets are rejected or destroyed.
The other mechanism, generally referred to as flow control, deals with the allocation of resources at the destination, such as memory and processing. Generally, in accordance with flow control, the destination sets a limit on the rate at which each source sending data to the destination may transmit that data. The sources and the destinations coordinate the transfer of data by an exchange of messages containing requests and acknowledgments. Before the source starts sending packets, it will send a request to the destination seeking permission to begin transmission. In response to the request, the destination sends a message containing an identification of the number of packets the source may dispatch toward the destination without, further authorization. This number is commonly referred to as the window size. The source then proceeds to transmit the authorized number of packets toward the destination and waits for the destination to verify their receipt. After the destination successfully receives a packet, it sends a message back to the source containing an acknowledgment indicating the successful receipt of the packet and, in some cases, authorizing the source to send another packet. In this way, the number of packets on the network traveling from the source toward the destination will never be more than the authorized window size.
Neither of these mechanisms, however, satisfactorily deals with the distribution of traffic within the network. Even with these mechanisms in place, on a busy network it is likely that many sources will simultaneously send traffic over the network to more than one destination. If too much of this traffic converges on a single router in too short a time, the limited buffer capacity of the router will be unable to cope with the volume and the router will reject or destroy the packets. When this happens, the network is said to be congested.
Then the network is congested, network performance degrades significantly. The affected sources have to retransmit the lost or rejected packets. Re-transmissions, however, necessarily use network resources such as buffer storage, processing time and link bandwidth to handle old traffic thereby leaving fewer resources for handling those portions of the messages still waiting to be transmitted for the first time. When that occurs, network delays increase drastically and network throughput drops. Indeed, since some network resources are being dedicated to handling re-transmissions at a time when the network is already experiencing a heavy load, there is a substantial risk of the congestion spreading and locking up the entire network.
A variety of alternative approaches exist for dealing with network congestion. Generally, the approaches fall into two categories. One category involves placing limitations on the amount of traffic which will be permitted on the network at any given time. Examples include the preallocation of buffers at the routers to ensure that memory is available to store arriving packets until they can be forwarded. The other category involves methods of limiting the spread of congestion once it occurs and then extricating the network from its congested state. The second category of approaches for dealing with network congestion is commonly referred to as congestion control. Congestion control typically involves feedback which signals the onset of congestion and instructs end systems to decrease the rate at which they initiate transmission of packets.
Currently, there are several schemes to avoid congestion and unnecessary delay for packets from low-bandwidth delay-sensitive TCP connections in the TCP/IP networks. Such proposals are described, for example, in M. Allman, V. Paxson, W. Stevens, xe2x80x9cTCP Congestion Controlxe2x80x9d, RFC2581, April 1999; Mathis, M., Mahdavi, J., Floyd, S., and Romanow, A., xe2x80x9cTCP Selective Acknowledgement Optionsxe2x80x9d, RFC 2018, October 1996; S. Floyd and T. Henderson, xe2x80x9cThe NewReno Modification to TCP""s Fast Recovery Algorithmxe2x80x9d, RFC2582, April 1999; Stevens, W., xe2x80x9cTCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithmsxe2x80x9d, RFC 2001, January 1997; K Ramakrishnan, S. Floyd, xe2x80x9cA Proposal To Add Explicit Congestion Notification (ECN) To IPxe2x80x9d, RFC 2481, April 1999; and Prasad Bagal, Shivkumar Kalyanaraman, Bob Packer, xe2x80x9cComparative study of RED, ECN and TCP Rate Controlxe2x80x9d, Technical Report, March 1999.
De facto standard implementations of TCP congestion control algorithms are described in RFC 2581 and RFC 2582, which employs both Fast Retransmit algorithm and Fast Recovery algorithm (FRFR), also known as Reno algorithms. These two algorithms rely on counting xe2x80x9cduplicate ACKsxe2x80x9dxe2x80x94TCP immediate acknowledge sent from the destination in response to each additional data segment received following missing data. Fast Retransmit and Fast Recovery (FRFR) algorithms are intended to preserve self-clock during recovery from a lost data segment. Fast Retransmit algorithm uses duplicate ACKs to detect the loss of a data segment. When three duplicate ACKs are detected, TCP assumes that a data segment has been lost and retransmit the lost packet, without waiting for a retransmission timer to expire. The Fast Recovery algorithm attempts to estimate how much data remains outstanding in the network by counting duplicate ACKs. The Fast Recovery algorithm artificially inflates the congestion window xe2x80x9cCWNDxe2x80x9d (i.e., TCP state variable that limits the amount of data a TCP source can send) on each duplicate ACK that is received, causing new data to be transmitted as the congestion window xe2x80x9cCWNDxe2x80x9d becomes large enough. Fast Recovery algorithm allows one (halved) window of new data to be transmitted following a Fast Retransmit. After the lost packet has been acknowledged, the congestion window xe2x80x9cCWNDxe2x80x9d should be reduced and the TCP source would come into the state of congestion avoidance. However, Reno algorithms and current modifications of Fast Retransmit/Fast Recovery (FRFR) algorithm are oriented to wired networks with very small transmission error, since the TCP assumes that the packet loss due to damage is extremely rare and the overwhelming majority of lost packets is due to congestion.
For wireless networks, however, TCP assumption is generally falsexe2x80x94most lost packets are due to errors that occur in the transmission of packets over error-prone media such as infrared or radio-frequency links, as opposed to network congestion. When these transmission errors occur, known as Bit Error Rate (BER), TCP mistakenly assumes that the network is congested and dramatically reduces its transmission of old and new packets. For example, whenever a packet is lost, TCP automatically resets its current window and threshold, then traps in the state of Slow-Start frequently, which may sharply degrade the throughput of connection. Although other congestion control algorithms are available to minimize the impact of losses from a throughput perspective, none is intended to distinguish the packet loss due to Bit Error Rate (BER) from loss due to congestion. As a result, TCP would still have to avoid the congestion that may not exist at all.
Accordingly, there is a need for a new and efficient mechanism provided to improve the TCP performance in high-speed packet-switched networks, especially wireless or mobile networks. A new algorithm is needed to distinguish congestion packets loss from individual packet loss due to Bit Error Rate (BER), to reject coming into Slow-Start and facilitate fast recovery when lost packets are due to Bit Error Rate (BER), and to reduce its sending speed as normal TCP upon occurrence of congestion so as to improve the throughput of connection in wireless and/or mobile networks.
Accordingly, various embodiments of the present invention are directed to a new recovery mechanism known as Fast Recovery Plus (FR+) algorithms and associated method, for wireless and/or mobile network applications to distinguish congestion packets loss from individual packet loss due to Bit Error Rate (BER), to advance fast data recovery when lost packets are due to Bit Error Rate (BER), and to reduce its sending speed as normal TCP upon occurrence of congestion so as to improve the throughput of connection while effectively avoiding network congestion in a TCP/IP packet-switched network such as wireless and/or mobile networks. Such enhanced Recovery Plus (FR+) algorithms may be installed or integrated into a host and/or a computer readable medium for use in a host for promoting fast data recovery while effectively controlling network congestion in packet-switched networks, especially wireless or mobile networks.
In accordance with an embodiment of the present invention, a method of flow control and congestion avoidance congestion in a network comprises the steps of: transmitting, at a source node, data packets to a destination node, via at least an intermediate node; receiving, at the destination node, data packets transmitted from the source node, via the intermediate node, and generating a duplicate ACK back to the source node to inform the source node that a data packet was received out-of-order in the network and serves as an indication that a data packet has been lost; upon receipt of a designated number of duplicate ACKs, at the source node, determining that a data packet has been lost; initializing a counter, at the source node, and recording a congestion window CWND, a slow start threshold Ssthresh, and a maximal sequence number SN that has been sent into the network; upon receipt of a next duplicate ACK, at the source node, recording its acknowledged sequence number ACK_SN; determining, at the source node, if the acknowledged sequence number ACK_SN is no more than a recorded sequence number SN; otherwise, incrementing the counter, at the source node, and re-transmitting a lost packet; if the acknowledged sequence number ACK_SN is no more than the recorded sequence number SN, determining if the packet loss is due to a transmission error; and if the packet loss is due to the transmission error, setting, at the source node, the slow start threshold Ssthresh to Max(CWND, (Ssthresh+CWND)/2), wherein said CWND and Ssthresh exhibit values previously recorded.
Specifically, the slow start threshold Ssthresh is set to no more than Max(FlightSize/2, 2*SMSS), wherein said FlightSize indicates the amount of outstanding data in the network, and said SMSS indicates the size of a largest data segment that can be transmitted. The counter is set to record the number of times of packet re-transmission invoked by the duplicate ACKs. In addition, packet loss is due to the transmission error, when the value of the counter is no more than a pre-defined packet threshold indicating the threshold of packet loss. Otherwise, packet loss is due to congestion in which case the congestion window CWND is reduced to halve, and a slow start threshold Ssthresh is reduced to the congestion window to slow a transmission rate to avoid congestion in the network.
In accordance with another embodiment of the present invention, a data network for wireless and/or mobile network applications may comprise a source node for transmitting data packets; a destination node for receiving the data packets from the source node and generating duplicate ACKs when the arrival of data packets is out-of-order; and at least one intermediate node disposed between said source node and said destination node; wherein said source node includes a Fast Recovery Plus (FR+) algorithm which, when activated upon receipt duplicate ACKs, performs the following: initializing a counter and recording a congestion window CWND, a slow start threshold Ssthresh, and a current maximal sequence number SN that has been sent into the network; upon receipt of a next duplicate ACK, recording its acknowledged sequence number ACK_SN; determining if the acknowledged sequence number ACK_SN is no less than a recorded sequence number SN; if the acknowledged sequence number ACK_SN is no less than the recorded sequence number SN, incrementing the counter, and re-transmitting a lost packet; if the acknowledged sequence number ACK_SN is no more than the recorded sequence number SN, determining if the packet loss is due to a transmission error; and if the packet loss is due to the transmission error, setting the slow start threshold Ssthresh to Max(CWND, (Ssthresh+CWND)/2), wherein said CWND and Ssthresh exhibit values previously recorded
In accordance with yet another embodiment, the present invention relates to a computer readable medium having an enhanced Fast Recovery Plus (FR+) algorithm stored therein for wireless network applications, when executed by a host system, performs the following: upon receipt of duplicate ACKs from a remote system, determining that a data packet has been lost; initializing a counter, and recording a congestion window CWND, a slow start threshold Ssthresh, and a maximal sequence number SN that has been sent into the network; upon receipt of a next. duplicate ACK, recording its acknowledged sequence number ACK_SN; determining if the acknowledged sequence number ACK_SN is no more than a recorded sequence number SN; if the acknowledged sequence number ACK_SN is more than the recorded sequence number SN, incrementing the counter, and retransmitting a lost packet; if the acknowledged sequence number ACK_SN is no more than the recorded sequence number SN, determining if the packet loss is due to a transmission error; and if the packet loss is due to the transmission error, setting the slow start threshold Ssthresh to Max(CWND, (Ssthresh+CWND)/2), wherein said CWND and Ssthresh exhibit values previously recorded.
The present invention is more specifically described in the following paragraphs by reference to the drawings attached only by way of example.